package dsg

import (
	"io"
	"fmt"
)

type PerfGraph struct {
      dg * DirGraph // 所有路径
      key * DirGraph // 关键路径

      size int
      etime_ []int
      etime [][]int

      te []int
      tl []int
}

func (pg * PerfGraph) pure_init (size int) {
      pg.size = size
      pg.etime_ = make ([]int, size * size)
      pg.etime = IndexIArray2D (pg.etime_, []int{size, size})
      pg.tl = make ([]int, size)
      pg.te = make ([]int, size)
}

func InitPerfGraph (size int) * PerfGraph {
      var pg PerfGraph 
      pg.dg = InitDirGraph (size)
      for i := 0; i < size; i ++ {
            pg.dg.AddNode (i)
      }
      pg.pure_init (size)
      return &pg
}

func (pg * PerfGraph) AddEdge (from, to int, time int) {
      pg.dg.AddEdge (from, to)
      pg.etime[from][to] = time
}

func (pg * PerfGraph) Save (fout io.Writer) {
      pg.dg.Save (fout)
      size := pg.size

      for i := 0; i < size; i ++ {
            for j := 0; j < size; j ++ {
                  fmt.Fprintf (fout, "%10d", pg.etime[i][j])
            }
            fmt.Fprintln (fout)
      }
      fmt.Fprintf (fout, "\n")
      
      if pg.key != nil {
            fmt.Fprintf (fout, "TimeRange\n\n")
      } else {
            fmt.Fprintf (fout, "NoTimeRange\n\n")
      }

      if pg.key != nil {
            for i := 0; i < size; i ++ {
                  fmt.Fprintf (fout, "%10d%10d\n", pg.te[i], pg.tl[i])
            }
            fmt.Fprintf (fout, "\n")
            pg.key.Save (fout)
      }

}

func LoadPerfGraph (fin io.Reader) * PerfGraph {
      var pg PerfGraph
      pg.dg = LoadDirGraph (fin)
      size := pg.dg.size
      pg.pure_init (size)

      for i := 0; i < size; i ++ {
            for j := 0; j < size; j ++ {
                  fmt.Fscan (fin, &pg.etime[i][j])
            }
      }

      var is_key_str string
      fmt.Fscan (fin, &is_key_str)
      if is_key_str == "TimeRange" {
            for i := 0; i < size; i ++ {
                  fmt.Fscan (fin, &pg.te[i], &pg.tl[i])
            }
            pg.key = LoadDirGraph (fin)
      }

      return &pg
}

func (pg * PerfGraph) CalNodeTimeRange () {
      size := pg.size

      dyn_graph := InitDirGraph (size)
      dyn_node := InitLList (size + 1)
      pg.key = InitDirGraph (size)

      // calculate te

      // init 
      nodes := pg.dg.GetAllNode ()
      edges := pg.dg.GetAllEdge ()
      for _, node := range nodes {
            dyn_graph.AddNode (node)
            ins := pg.dg.GetInEdge (node)
            if len(ins) == 0 {
                  dyn_node.Push (node)
            }
      }
      for _, edge := range edges {
            dyn_graph.AddEdge (edge[0], edge[1])
      }


      for {
            pnode := dyn_node.PopFirst ()
            if pnode == nil {break}
            node := pnode.(int)
            ins := pg.dg.GetInEdge (node)
            pg.te[node] = 0
            for _, in := range ins {
                  t := pg.te[in] + pg.etime[in][node]
                  if t > pg.te[node] {
                        pg.te[node] = t
                  }
            }
            outs := pg.dg.GetOutEdge (node)
            for _, out := range outs {
                  dyn_graph.RemoveEdge (node, out)
                  if dyn_graph.Edge.GetColNum (out) == 0 {
                        dyn_node.Push (out)
                  }
            }
      }

      n := dyn_graph.Edge.GetNum ()
      if  n != 0 {
            panic ("algorithm error")
      }

      // calculate tl

      // reinit 

      for _, node := range nodes {
            outs := pg.dg.GetOutEdge (node)
            if len(outs) == 0 {
                  dyn_node.Push (node)
            }
      }
      for _, edge := range edges {
            dyn_graph.AddEdge (edge[0], edge[1])
      }

      for {
            pnode := dyn_node.PopFirst ()
            if pnode == nil {break}
            node := pnode.(int)
            outs := pg.dg.GetOutEdge (node)
            pg.tl[node] = pg.te[node]
            max_out := -1
            for _, out := range outs {
                  t := pg.tl[out] - pg.etime[node][out]
                  if max_out < 0 || t < pg.tl[node] {
                        pg.tl[node] = t
                        max_out = out
                  }
            }

            // add key node and key edge
            if pg.tl[node] == pg.te[node] {
                  pg.key.AddNode (node)
                  if max_out != -1 {
                        pg.key.AddEdge (node, max_out)
                  }
            }

            ins := pg.dg.GetInEdge (node)
            for _, in := range ins {
                  dyn_graph.RemoveEdge (in, node)
                  if dyn_graph.Edge.GetRowNum (in) == 0 {
                        dyn_node.Push (in)
                  }
            }
      }

}

